package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/buddy-strings/'>亲密字符串(Buddy Strings)</a>
 * <p>给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。</p>
 * <p>
 * 交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
 *     <ul>
 *         <li>例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。</li>
 *     </ul>
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "ab", goal = "ba"
 *      输出：true
 *      解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。
 *
 * 示例 2：
 *      输入：s = "ab", goal = "ab"
 *      输出：false
 *      解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。
 *
 * 示例 3：
 *      输入：s = "aa", goal = "aa"
 *      输出：true
 *      解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= s.length, goal.length <= 2 * 10^4</li>
 *         <li>s 和 goal 由小写英文字母组成</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/18 15:21
 */
public class LC0859BuddyStrings_S {

    static class Solution {
        public boolean buddyStrings(String s, String goal) {
            // 如果满足交换 s[i] 和 s[j] 后两个字符串相等，那么需要满足以下几个条件使得 s 和 goal 为亲密字符串：
            /*
                1.当 s 与 goal 长度 或 词频不同，必然不为亲密字符；
                2.当「s 与 goal 不同的字符数量为 2（能够相互交换）」
                  或「s 与 goal 不同的字符数量为 0，但同时 s 中有出现数量超过 2 的字符（能够相互交换）」时，两者必然为亲密字符。
             */
            if (s.length() != goal.length()) {
                return false;
            }
            // 如果 s 和 goal相同；则只能某个字母，出现两次以及上，相同字母进行交换。否则，返回false
            if (s.equals(goal)) {
                int[] record = new int[26];
                for (int i = 0; i < s.length(); i++) {
                    int index = s.charAt(i) - 'a';
                    // 如果相同字符出现了 2次或以上，则可以同字母交换
                    if (record[index] == 1) {
                        return true;
                    }
                    record[index]++;
                }
                return false;
            }
            // 如果 s 和 goal不同；则只允许出现不同位置的字母恰好为2
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            //s 和 goal 同一位置不同字母出现的次数
            int diff = 0;
            for (int i = 0; i < s.length(); i++) {
                int a = s.charAt(i) - 'a';
                int b = goal.charAt(i) - 'a';
                cnt1[a]++;
                cnt2[b]++;
                if (a != b) {
                    if (diff == 2) {
                        return false;
                    }
                    diff++;
                }
            }
            // 判断次品是否相同
            for (int i = 0; i < 26; i++) {
                // 词频不同，直接返回 false。例如：s中出现了 a，goal中未出现，再怎么交换也不会相同
                if (cnt1[i] != cnt2[i]) {
                    return false;
                }
            }
            return true;
        }
    }
}
